home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / usenet / sources / volume90 / aplictns / route_10 / part03 / solve.c < prev   
C/C++ Source or Header  |  1990-04-23  |  13KB  |  433 lines
  1. #include <stdio.h>
  2.  
  3. #ifndef M_XENIX
  4. /*
  5. #include <stdlib.h>
  6. #include <io.h>
  7. */
  8. #endif 
  9.  
  10. #include <fcntl.h>
  11. #include "cell.h"
  12.  
  13. /*
  14. ** visit neighboring cells like this (where [9] is on the other side):
  15. **
  16. **    +---+---+---+
  17. **    | 1 | 2 | 3 |
  18. **    +---+---+---+
  19. **    | 4 |[9]| 5 |
  20. **    +---+---+---+
  21. **    | 6 | 7 | 8 |
  22. **    +---+---+---+
  23. */
  24.  
  25. static int delta[8][2] = { /* for visiting neighbors on the same side */
  26.      {  1, -1 }, /* northwest    */
  27.      {  1,  0 }, /* north        */
  28.      {  1,  1 }, /* northeast    */
  29.      {  0, -1 }, /* west        */
  30.      {  0,  1 }, /* east        */
  31.      { -1, -1 }, /* southwest    */
  32.      { -1,  0 }, /* south        */
  33.      { -1,  1 }  /* southeast    */
  34.     };
  35.  
  36. static int ndir[8] = { /* for building paths back to source */
  37.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  38.      FROM_EAST,                  FROM_WEST,
  39.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  40.     };
  41.  
  42. /* blocking masks for neighboring cells */
  43. #define BLOCK_NORTHEAST        ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  44.                 | ANGLE_NEtoSE | ANGLE_NWtoNE \
  45.                 | SHARP_NtoNE | SHARP_EtoNE )
  46. #define BLOCK_SOUTHEAST        ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  47.                 | ANGLE_NEtoSE | ANGLE_SEtoSW \
  48.                 | SHARP_EtoSE | SHARP_StoSE )
  49. #define BLOCK_SOUTHWEST        ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  50.                 | ANGLE_SEtoSW | ANGLE_SWtoNW \
  51.                 | SHARP_StoSW | SHARP_WtoSW )
  52. #define BLOCK_NORTHWEST        ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  53.                 | ANGLE_SWtoNW | ANGLE_NWtoNE \
  54.                 | SHARP_WtoNW | SHARP_NtoNW )
  55.  
  56. struct block {
  57.     int r1, c1;
  58.     long b1, h1;
  59.     int r2, c2;
  60.     long b2, h2;
  61.     };
  62.  
  63. static struct block blocking[8] = { /* blocking masks */
  64.      {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  65.         1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
  66.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  67.      {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  68.         0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  69.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  70.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  71.      {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  72.        -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  73.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  74.      { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  75.         0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
  76.     };
  77.  
  78. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  79.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  80.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  81.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  82.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  83.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  84.     };
  85.  
  86. static long newmask[5][8] = { /* patterns to mask out in neighbor cells */
  87.      { 0, 0, 0, 0, 0, 0, 0, 0 },
  88.      { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
  89.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  90.      { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
  91.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  92.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
  93.         CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
  94.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
  95.         CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
  96.     };
  97.  
  98. static char fmt[] =
  99.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  100.  
  101. /* board dimensions */
  102. extern int Nrows;
  103. extern int Ncols;
  104.  
  105. /* measures of progress */
  106. int Ntotal = 0;
  107. int Ncurrent = 0;
  108.  
  109. /* search statistics */
  110. extern long OpenNodes; /* total number of nodes opened */
  111. extern long ClosNodes; /* total number of nodes closed */
  112. extern long MoveNodes; /* total number of nodes moved */
  113. extern long MaxNodes; /* maximum number of nodes opened at one time */
  114.  
  115. extern int one_side; /* udi 27-2-90 - single sides board flag */
  116.  
  117. extern void GetWork();
  118.  
  119. extern void InitQueue();
  120. extern void GetQueue();
  121. extern void SetQueue();
  122. extern void ReSetQueue();
  123. extern long GetCell();
  124. extern void SetCell();
  125. extern void OrCell();
  126. extern int GetDir();
  127. extern void SetDir();
  128. extern int GetDist();
  129. extern void SetDist();
  130. extern int GetApxDist();
  131. extern int CalcDist();
  132.  
  133. void Solve();
  134. void Retrace();
  135.  
  136. void Solve () { /* route all traces */
  137.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  138.     int i;
  139.     char *n1;
  140.     char *n2;
  141.     long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  142.     int newdist, olddir, success, self, echo;
  143.  
  144.     printf( "enter Solve()\n" );
  145.     echo = isatty( fileno(stdout) ) ? 1 : 0;
  146.     /* go until no more work to do */
  147.     while () {
  148.         GetWork( &r1, &c1, &n1, &r2, &c2, &n2 );
  149.         if (r1 == ILLEGAL) break;
  150.         Ncurrent++;
  151.         printf( "routing %s=%s, %d of %d\n", n1, n2, Ncurrent,
  152.             Ntotal );
  153.         if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  154.             continue;
  155.         success = 0;
  156.         lastopen = lastclos = lastmove = 0;
  157.         InitQueue(); /* initialize the search queue */
  158.         a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  159.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  160.         if (!one_side) SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  161.         /* search until success or we exhaust all possibilities */
  162.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  163.             GetQueue( &r, &c, &s, &d, &a )) {
  164.             if (r == r2 && c == c2) { /* success! */
  165.                 Retrace( r1, c1, r2, c2, s ); /* lay traces */
  166.                 success++;
  167.                 break;
  168.                 }
  169.             /* report every 100 new nodes or so */
  170.             if (echo && (OpenNodes - lastopen > 100
  171.                 || ClosNodes - lastclos > 100
  172.                 || MoveNodes - lastmove > 100)) {
  173.                 lastopen = (OpenNodes/100)*100;
  174.                 lastclos = (ClosNodes/100)*100;
  175.                 lastmove = (MoveNodes/100)*100;
  176.                 printf( fmt, OpenNodes, ClosNodes,
  177.                     MoveNodes, MaxNodes,
  178.                     (ClosNodes*50)/(Nrows*Ncols) );
  179.                 putchar( '\r' );
  180.                 }
  181.             curcell = GetCell( r, c, s );
  182.             if (curcell & CORNER_NORTHWEST)
  183.                 self = 1;
  184.             else if (curcell & CORNER_NORTHEAST)
  185.                 self = 2;
  186.             else if (curcell & CORNER_SOUTHWEST)
  187.                 self = 3;
  188.             else if (curcell & CORNER_SOUTHEAST)
  189.                 self = 4;
  190.             else
  191.                 self = 0;
  192.             for (i = 0; i < 8; i++) { /* consider neighbors */
  193.                 if (!selfok[self][i]) /* check self-block */
  194.                     continue;
  195.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  196.                     || (nc = c+delta[i][1]) < 0
  197.                     || nc >= Ncols) /* off the edge? */
  198.                     continue;
  199.                 newcell = GetCell( nr, nc, s );
  200.                 /* check for non-target hole */
  201.                 if (newcell & HOLE) {
  202.                     if (nr != r2 || nc != c2)
  203.                         continue;
  204.                     }
  205.                 else {
  206.                     newcell &= ~(newmask[self][i]);
  207.                     if (newcell) /* check for traces */
  208.                         continue;
  209.                     }
  210.                 /* check blocking on corner neighbors */
  211.                 if (delta[i][0] && delta[i][1]) {
  212.                     /* check first buddy */
  213.                     buddy = GetCell( r+blocking[i].r1,
  214.                         c+blocking[i].c1, s );
  215.                     if (buddy & HOLE) {
  216.                         if (buddy & (blocking[i].h1))
  217.                             continue;
  218.                         }
  219.                     else if (buddy & (blocking[i].b1))
  220.                         continue;
  221.                     /* check second buddy */
  222.                     buddy = GetCell( r+blocking[i].r2,
  223.                         c+blocking[i].c2, s );
  224.                     if (buddy & HOLE) {
  225.                         if (buddy & (blocking[i].h2))
  226.                             continue;
  227.                         }
  228.                     else if (buddy & (blocking[i].b2))
  229.                         continue;
  230.                     }
  231.                 olddir = GetDir( r, c, s );
  232.                 newdist = d+CalcDist( ndir[i], olddir,
  233.                     (olddir == FROM_OTHERSIDE)
  234.                     ? GetDir( r, c, 1-s ) : 0 );
  235.                 /* if not visited yet, add it to queue */
  236.                 if (!GetDir( nr, nc, s )) {
  237.                     SetDir( nr, nc, s, ndir[i] );
  238.                     SetDist( nr, nc, s, newdist );
  239.                     SetQueue( nr, nc, s, newdist,
  240.                         GetApxDist( nr, nc, r2, c2 ),
  241.                         r2, c2 );
  242.                     }
  243.                 /* we might have found a better path */
  244.                 else if (newdist < GetDist( nr, nc, s )) {
  245.                     SetDir( nr, nc, s, ndir[i] );
  246.                     SetDist( nr, nc, s, newdist );
  247.                     ReSetQueue( nr, nc, s, newdist,
  248.                         GetApxDist( nr, nc, r2, c2 ),
  249.                         r2, c2 );
  250.                     }
  251.                 }
  252.             /* consider other side of board */
  253.             /* check for holes or traces on other side */
  254. /* udi 27-2-90 - add support or single sides boards.
  255.             if (newcell = GetCell( r, c, 1-s ))
  256. */
  257.             if ((newcell = GetCell( r, c, 1-s )) || one_side)
  258.                 continue;
  259.             skip = 0;
  260.             /* check for nearby holes */
  261.             for (i = 0; i < 8; i++) {
  262.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  263.                     || (nc = c+delta[i][1]) < 0
  264.                     || nc >= Ncols) /* off the edge? */
  265.                     continue;
  266.                 if (GetCell( nr, nc, s ) & HOLE) {
  267.                     skip = 1; /* neighboring hole */
  268.                     break;
  269.                     }
  270.                 }
  271.             if (skip) /* neighboring hole? */
  272.                 continue; /* yes, can't drill one here */
  273.             olddir = GetDir( r, c, s );
  274.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
  275.                 (olddir == FROM_OTHERSIDE)
  276.                 ? GetDir( r, c, 1-s ) : 0 );
  277.             /* if not visited yet, add it to queue */
  278.             if (!GetDir( r, c, 1-s )) {
  279.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  280.                 SetDist( r, c, 1-s, newdist );
  281.                 SetQueue( r, c, 1-s, newdist, a, r2, c2 );
  282.                 }
  283.             /* we might have found a better path */
  284.             else if (newdist < GetDist( r, c, 1-s )) {
  285.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  286.                 SetDist( r, c, 1-s, newdist );
  287.                 ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
  288.                 }
  289.             }
  290.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  291.             (ClosNodes*50)/(Nrows*Ncols) );
  292.         putchar( '\n' );
  293.         if (!success)
  294.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  295.         /* clear direction flags */
  296.         for (r = 0; r < Nrows; r++) {
  297.             for (c = 0; c < Ncols; c++) {
  298.                 SetDir( r, c, TOP, EMPTY );
  299.                 SetDir( r, c, BOTTOM, EMPTY );
  300.                 }
  301.             }
  302.         }
  303.     printf( "leave Solve()\n" );
  304.     }
  305.  
  306. static long bit[8][9] = { /* OT=Otherside */
  307.      /* N, NE, E, SE, S, SW, W, NW, OT */
  308. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  309.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  310. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  311.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  312. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  313.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  314. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  315.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  316. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  317.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  318. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  319.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  320. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  321.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  322. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  323.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  324.     };
  325.  
  326. void Retrace ( rr1, cc1, rr2, cc2, s )
  327.     /* work from target back to source, actually laying the traces */
  328.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  329.     {
  330.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  331.     register int x, y;
  332.     long b;
  333.  
  334.     r1 = rr2;
  335.     c1 = cc2;
  336.     s1 = s;
  337.     r0 = c0 = s0 = ILLEGAL;
  338.     do {
  339.         /* find where we came from to get here */
  340.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  341.         case FROM_NORTH:    r2++;        break;
  342.         case FROM_EAST:            c2++;    break;
  343.         case FROM_SOUTH:    r2--;        break;
  344.         case FROM_WEST:            c2--;    break;
  345.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  346.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  347.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  348.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  349.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  350.         default:
  351.             printf( "internal error: no way back\n" );
  352.             exit( -1 );
  353.             break;
  354.             }
  355.         if (r0 != ILLEGAL)
  356.             y = GetDir( r0, c0, s0 );
  357.         /* see if target or hole */
  358.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  359.             switch (x) {
  360.             case FROM_NORTH:
  361.                 OrCell( r1, c1, s1, HOLE_NORTH );    break;
  362.             case FROM_EAST:
  363.                 OrCell( r1, c1, s1, HOLE_EAST );    break;
  364.             case FROM_SOUTH:
  365.                 OrCell( r1, c1, s1, HOLE_SOUTH );    break;
  366.             case FROM_WEST:
  367.                 OrCell( r1, c1, s1, HOLE_WEST );    break;
  368.             case FROM_NORTHEAST:
  369.                 OrCell( r1, c1, s1, HOLE_NORTHEAST );    break;
  370.             case FROM_SOUTHEAST:
  371.                 OrCell( r1, c1, s1, HOLE_SOUTHEAST );    break;
  372.             case FROM_SOUTHWEST:
  373.                 OrCell( r1, c1, s1, HOLE_SOUTHWEST );    break;
  374.             case FROM_NORTHWEST:
  375.                 OrCell( r1, c1, s1, HOLE_NORTHWEST );    break;
  376.             case FROM_OTHERSIDE:
  377.             default:
  378.                 printf( "internal error\n" );
  379.                 exit( -1 );
  380.                 break;
  381.                 }
  382.             }
  383.         else {
  384.             if ((y == FROM_NORTH || y == FROM_NORTHEAST
  385.                 || y == FROM_EAST || y == FROM_SOUTHEAST
  386.                 || y == FROM_SOUTH || y == FROM_SOUTHWEST
  387.                 || y == FROM_WEST || y == FROM_NORTHWEST)
  388.                 && (x == FROM_NORTH || x == FROM_NORTHEAST
  389.                 || x == FROM_EAST || x == FROM_SOUTHEAST
  390.                 || x == FROM_SOUTH || x == FROM_SOUTHWEST
  391.                 || x == FROM_WEST || x == FROM_NORTHWEST
  392.                 || x == FROM_OTHERSIDE)
  393.                 && (b = bit[y-1][x-1])) {
  394.                 OrCell( r1, c1, s1, b );
  395.                 if (b & HOLE)
  396.                     OrCell( r2, c2, s2, HOLE );
  397.                 }
  398.             else {
  399.                 printf( "internal error\n" );
  400.                 exit( -1 );
  401.                 }
  402.             }
  403.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  404.             switch (x) {
  405.             case FROM_NORTH:
  406.                 OrCell( r2, c2, s2, HOLE_SOUTH );    break;
  407.             case FROM_EAST:
  408.                 OrCell( r2, c2, s2, HOLE_WEST );    break;
  409.             case FROM_SOUTH:
  410.                 OrCell( r2, c2, s2, HOLE_NORTH );    break;
  411.             case FROM_WEST:
  412.                 OrCell( r2, c2, s2, HOLE_EAST );    break;
  413.             case FROM_NORTHEAST:
  414.                 OrCell( r2, c2, s2, HOLE_SOUTHWEST );    break;
  415.             case FROM_SOUTHEAST:
  416.                 OrCell( r2, c2, s2, HOLE_NORTHWEST );    break;
  417.             case FROM_SOUTHWEST:
  418.                 OrCell( r2, c2, s2, HOLE_NORTHEAST );    break;
  419.             case FROM_NORTHWEST:
  420.                 OrCell( r2, c2, s2, HOLE_SOUTHEAST );    break;
  421.             case FROM_OTHERSIDE:
  422.             default:
  423.                 printf( "internal error\n" );
  424.                 exit( -1 );
  425.                 break;
  426.                 }
  427.             }
  428.         /* move to next cell */
  429.         r0 = r1; c0 = c1; s0 = s1;
  430.         r1 = r2; c1 = c2; s1 = s2;
  431.         } while (!(r2 == rr1 && c2 == cc1));
  432.     }
  433.